/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: OR25 左右最值最大差
 * <a href="https://www.nowcoder.com/practice/f5805cc389394cf69d89b29c0430ff27?tpId=182&tqId=34751&ru=/exam/oj">...</a>
 * User: DELL
 * Date: 2023-05-19
 * Time: 23:44
 */
public class MaxGap {
    /**
     * 解题思路 (贪心算法)
     * 首先找到最大值以及最大值所在的位置pos：
     * 1.如果pos=0，那么最大差值肯定是A[[0]-A[n-1]，因为左部分最大值必然是A[0]，
     * 右部分必然要包含A[n-1]，那么右部分最大值只会>=A[n-1]
     * 2.如果pos=n-1，那么最大差值肯定是A[n-1]-A[0]，道理和1一样
     * 3.如果pos是在中间位置，那么就是取(A[pos] - A[0]) 和(A[pos] - A[n-1])中最大的一个
     * @param A
     * @param n
     * @return
     */
    public int findMaxGap(int[] A, int n) {
        int max = A[0];
        int pos = 0;
        for (int i = 1; i < n; i++) {
            if (A[i] > max) {
                max = A[i];
                pos = i;
            }
        }
        //分类讨论
        if (pos == 0) {
            return max-A[n-1];
        } else if (pos == n-1) {
            return max-A[0];
        } else {
            return Math.max(max-A[n-1],max-A[0]);
        }
    }
}